package leetcode.code0450;

import leetcode.IDebug;
import leetcode.helper.H;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

/**
 * 折了。
 * @author CaoYu
 * @date 2022年6月2日
 * @description 
 */
public class Solution2 implements IDebug {

	public TreeNode deleteNode(TreeNode root, int key) {
		// 目标，目标上级，目标next，目标next上级
		TreeNode[] find = new TreeNode[4];
		this.deleteNode(root, key, null, find);
		TreeNode keyNode = find[0], keyNodeP = find[1];
		TreeNode nextNode = find[2], nextNodeP = find[3];
		if (keyNode == null) {
			return root;
		} else if (keyNode == root) {
			if (nextNode == null) {
				return keyNode.left;
			} else if (nextNodeP == keyNode) {
//				keyNodeP.left = nextNode;
				nextNode.left = keyNode.left;
				return nextNode;
			} else {
				nextNodeP.left = null;
				nextNode.left = keyNode.left;
				nextNode.right = keyNode.right;
				return nextNode;
			}
		} else {
			if (nextNode == null) {
				if (keyNodeP.val > keyNode.val) {
					keyNodeP.left = nextNode;
				} else {
					keyNodeP.right = nextNode;
				}
				return root;
			} else if (nextNodeP == keyNode) {
				if (keyNodeP.val > nextNode.val) {
					keyNodeP.left = nextNode;
					nextNode.left = keyNode.left;
				} else {
					keyNodeP.right = nextNode;
					nextNode.left = keyNode.left;
				}
				return root;
			} else if (nextNode == keyNodeP) {
				nextNode.left = keyNode.left;
				return root;
			} else {
				if (keyNode.left == null && keyNode.right == null) {
					if (keyNodeP.val > key) {
						keyNodeP.left = null;
					} else {
						keyNodeP.right = null;
					}
					return root;
				}
				if (keyNodeP.val > nextNode.val) {
					keyNodeP.left = nextNode;
				} else {
					keyNodeP.right = nextNode;
				}
				if (nextNodeP.val > nextNode.val) {
					nextNodeP.left = nextNode.right;
				} else {
					nextNodeP.right = nextNode.right;
				}
				nextNode.left = keyNode.left;
				nextNode.right = keyNode.right;
				return root;
			}
		}
	}

	private void deleteNode(TreeNode me, int key, TreeNode myRoot, TreeNode[] find) {
		if (me == null) {
			return;
		}
		if (me.val > key) {
			if (find[2] == null || find[2].val > me.val) {
				find[2] = me;
				find[3] = myRoot;
			}
			this.deleteNode(me.left, key, me, find);
		} else if (me.val < key) {
			this.deleteNode(me.right, key, me, find);
		} else {
			find[0] = me;
			find[1] = myRoot;
			this.deleteNode(me.right, key, me, find);
		}
	}

	@Override
	public void debug4() {
		this.deleteNode(TreeArray.array2tree(H.str2array4(
				"[2,0,33,null,1,25,40,null,null,11,31,34,45,10,18,29,32,null,36,43,46,4,null,12,24,26,30,null,null,35,39,42,44,null,48,3,9,null,14,22,null,null,27,null,null,null,null,38,null,41,null,null,null,47,49,null,null,5,null,13,15,21,23,null,28,37,null,null,null,null,null,null,null,null,8,null,null,null,17,19,null,null,null,null,null,null,null,7,null,16,null,null,20,6]")),
				33);
		this.deleteNode(TreeArray.array2tree(H.str2array4("[3,2,4,1]")), 2);
		this.deleteNode(TreeArray.array2tree(H.str2array4("[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]")), 6);

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
//		[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
